//
//  MirrorTree.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/7/19.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  剑指 Offer 27. 二叉树的镜像

import UIKit

/*
 剑指 Offer 27. 二叉树的镜像
 
 请完成一个函数，输入一个二叉树，该函数输出它的镜像。

 例如输入：

      4
    /   \
   2     7
  / \   / \
 1   3 6   9
 镜像输出：

      4
    /   \
   7     2
  / \   / \
 9   6 3   1

  

 示例 1：

 输入：root = [4,2,7,1,3,6,9]
 输出：[4,7,2,9,6,3,1]
 */

class MirrorTree: NSObject {
    //以下方法提交8ms
    func mirrorTree(_ root: TreeNode?) -> TreeNode? {

        guard root != nil else {
            return nil
        }
        
        let left = self.mirrorTree(root?.right)
        let right = self.mirrorTree(root?.left)
        
        root?.left = left
        root?.right = right
        
        return root
        
    }
    
    //以下方法提交4ms
    func mirrorTree2(_ root: TreeNode?) -> TreeNode? {

        guard root != nil else {
            return nil
        }
        
        let tmp = root?.left
        root?.left = self.mirrorTree(root?.right)
        root?.right = self.mirrorTree(tmp)
        
        return root
        
    }
    
    
    
    //辅助栈解法4ms
    func mirrorTree3(_ root: TreeNode?) -> TreeNode? {

        guard root != nil else {
            return nil
        }
        
        let stack = CStack()
        stack.push(root)
        
        while stack.isEmpty == false {
            let node = stack.pop()
            if node?.left != nil {
                stack.push(node?.left)
            }
            if node?.right != nil {
                stack.push(node?.right)
            }
            let tmp = node?.left
            node?.left = node?.right
            node?.right = tmp
        }
        
        return root
        
    }
}

public class CStack: NSObject{
    public var stackSource: Array<TreeNode> = []
    public var size:Int{
        return stackSource.count
    }
    public var isEmpty: Bool{
        return stackSource.count == 0
    }
    
    public func push(_ elememt: TreeNode?){
        stackSource.append(elememt!)
    }
    
    public func pop() -> TreeNode?{
        if let last = stackSource.last{
            stackSource.removeLast()
            return last
            
        }else{
            return TreeNode(0)
        }
    }
    
}
